Decision Procedure

释义 Definition

decision procedure（判定程序/决策程序）：在逻辑学、数学与计算机科学中，指一种明确、可执行的算法或步骤，用于在有限时间内对某类问题给出“是/否”（可判定/不可判定、成立/不成立）的结论。（在日常语境中也可泛指“做决定的程序”，但更常见于形式化学科。）

发音 Pronunciation (IPA)

/dsn prsidr/

例句 Examples

We need a decision procedure to check whether the formula is satisfiable.
我们需要一个判定程序来检查该公式是否可满足。

Although the rules look simple, finding a decision procedure for the entire logic can be impossible.
尽管规则看起来很简单，但为整个逻辑找到一个判定程序可能是不可能的。

词源 Etymology

decision 来自拉丁语 decidere（“切开、裁决”，引申为“作出决定”）；procedure 来自拉丁语 procedere（“向前进行”）。合起来在20世纪逻辑学与计算理论语境中固定为术语，表示“用明确步骤作出可终止的判定”。

相关词 Related Words

• Algorithm
• Decidable
• Decision Problem
• Procedure
• Satisfiable
• Undecidable

文学与经典著作 Literary Works

• Alonzo Church（丘奇）关于“判定问题（Entscheidungsproblem）”的论文中讨论与“decision procedure”密切相关的概念（如 An Unsolvable Problem of Elementary Number Theory, 1936）。
• Alan Turing（图灵）在 On Computable Numbers, with an Application to the Entscheidungsproblem（1936）中围绕“是否存在一般性的判定程序”展开论证。
• Michael Sipser, Introduction to the Theory of Computation 中在“可判定性/不可判定性”章节频繁使用该术语或同义表达。